package 图;

import 抽象数据类型.Graph;

import java.util.Stack;

/**
 * @author: yangwk
 * @date: 2023/4/4
 * @description:
 **/
public class 深度优先遍历 {
    //深度有限
    public static class DepthFirstPaths {
        private final boolean[] marked;
        private final int[] edgeTo;//从起点到一个顶点的一直路径上的最后一个顶点
        private final int s;//起点

        public DepthFirstPaths(Graph graph, int s) {
            marked = new boolean[graph.V()];
            edgeTo = new int[graph.V()];
            this.s = s;
            dfs(graph, s);
        }

        private void dfs(Graph graph, int v) {
            marked[v] = true;
            for (Integer w : graph.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    dfs(graph, w);
                }
            }
        }

        public boolean hasPathTo(int v) {
            return marked[v];
        }

        public Iterable<Integer> pathTo(int v) {
            if (!hasPathTo(v)) {
                return null;
            }
            Stack<Integer> path = new Stack<>();
            for (int x = v; x != s; x = edgeTo[x]) {
                path.push(x);
            }
            path.push(s);
            return path;
        }

    }
}
